﻿using System;
using System.Collections.Generic;
using System.Linq;

namespace Huffman
{
	
	public class Tree<T> : IComparable
	{
		public T Node{get; private set;}
		private Tree<T> Left;
		private Tree<T> Right;
		public int Count{get; private set;}
		
		public Tree(Tree<T> left, Tree<T> right, int count)
		{
			Left = left;
			Right = right;
			Count = count;
		}
		
		public Tree(T node, int count)
		{
			Node = node;
			Count = count;
		}
		
		public bool isEndNode()
		{
			return Node != null;
		}
		
		public int CompareTo(object obj)
		{
			if (obj == null) return 1;
			Tree<T> other = obj as Tree<T>;
			if (other != null) 
	            return this.Count.CompareTo(other.Count);
	        else
	           throw new ArgumentException("Types are not the same");
		}
	}
	
	public class Calculator
	{
		public static Dictionary<T, int> CalcFrequency<T>(IEnumerable<T> source)
		{
			Dictionary<T, int> result = new Dictionary<T, int>();
			foreach (T i in source)
			{
				if (result.ContainsKey(i))
				{
					result[i] += 1;
				}
				else
				{
					result[i] = 1;
				}
			}
			return result;
		}
		
		public static IEnumerable<Tree<T>> WrapDictionaryEntries<T>(Dictionary<T, int> source)
		{
			return (from entry in source select new Tree<T>(entry.Key, entry.Value) );
		}
	}
	
	public class SortedTreeList<T>
	{
		public Tree<T> Node {get; private set;}
		private SortedTreeList<T> next;
		
		private SortedTreeList(Tree<T> _node, SortedTreeList<T> _next)
		{
			Node = _node;
			next = _next;
		}
		
		private void assign(SortedTreeList<T> source)
		{
			if (source == null) throw new ArgumentNullException();
			this.Node = source.Node;
			this.next = source.next;
		}
		
		public SortedTreeList(IEnumerable<Tree<T>> source)
		{
			var t = (from entry in source orderby entry descending select entry);
			SortedTreeList<T> currentNext = null;
			foreach (Tree<T> i in t)
			{
				currentNext = new SortedTreeList<T>(i, currentNext);
			}
			this.assign(currentNext);
		}
		
		public void PutNode(Tree<T> newNode)
		{
			SortedTreeList<T> current = this, prev = null;
			while (newNode.CompareTo(current.Node) > 0)
			{
				prev = current;
				current = current.next;
			}
			if (prev!=null)
				prev.next = new SortedTreeList<T>(newNode, current);
			else
				this.assign(new SortedTreeList<T>(newNode, current));
		}
		
		public Tree<T> Top()
		{
			Tree<T> r = Node;
			this.assign(next);
			return r;
		}
		
		public bool hasAtLeastTwoNodes()
		{
			return (next != null);
		}
	}
	
	public class HuffmanTreeBuilder<T>
	{
		private  SortedTreeList<T> treeList;
			
		public HuffmanTreeBuilder(IEnumerable<T> source)
		{
			treeList = new SortedTreeList<T>(Calculator.WrapDictionaryEntries(Calculator.CalcFrequency(source)));
		}
		
		private void makeIteration()
		{
			Tree<T> first = treeList.Top();
			Tree<T> second = treeList.Top();
			treeList.PutNode(new Tree<T>(first, second, first.Count + second.Count));
		}
		
		public Tree<T> ResultTree()
		{
			while(treeList.hasAtLeastTwoNodes())
				makeIteration();
			return treeList.Node;
		}
	}
}